package org.jheaps.tree

import org.jheaps.AddressableHeap
import org.jheaps.annotations.ConstantTime
import org.jheaps.annotations.LogarithmicTime
import java.io.Serializable

/**
 * An explicit d-ary tree addressable heap. The heap is sorted according to the
 * [natural ordering][Comparable] of its keys, or by a
 * [Comparator] provided at heap creation time, depending on which
 * constructor is used.
 *
 *
 *
 * The worst-case cost of `insert`, `deleteMin`, `delete` and
 * `decreaceKey` operations is O(d log_d(n)) and the cost of `findMin`
 * is O(1).
 *
 *
 *
 * Note that the ordering maintained by a binary heap, like any heap, and
 * whether or not an explicit comparator is provided, must be *consistent
 * with `equals`* if this heap is to correctly implement the
 * `Heap` interface. (See `Comparable` or `Comparator` for a
 * precise definition of *consistent with equals*.) This is so because
 * the `Heap` interface is defined in terms of the `equals`
 * operation, but a binary heap performs all key comparisons using its
 * `compareTo` (or `compare`) method, so two keys that are deemed
 * equal by this method are, from the standpoint of the binary heap, equal. The
 * behavior of a heap *is* well-defined even if its ordering is
 * inconsistent with `equals`; it just fails to obey the general contract
 * of the `Heap` interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 * @param <V>
 * the type of values maintained by this heap
 *
 * @author Dimitrios Michail
 *
 * @see AddressableHeap
 *
 * @see Comparable
 *
 * @see Comparator
</V></K> */
class DaryTreeAddressableHeap<K, V> @JvmOverloads constructor(d: Int,
                                                              /**
                                                               * The comparator used to maintain order in this heap, or null if it uses
                                                               * the natural ordering of its keys.
                                                               *
                                                               * @serial
                                                               */
                                                              private val comparator: Comparator<in K?>? = null
) : AddressableHeap<K,V>, Serializable {

    /**
     * Size of the heap
     */
    private var size: Long

    /**
     * Root node of the heap
     */
    private var root: Node?

    /**
     * Branching factor. Always a power of two.
     */
    private val d: Int

    /**
     * Base 2 logarithm of branching factor.
     */
    private val log2d: Int

    /**
     * Auxiliary for swapping children.
     */
    private val aux: Array<Node?>

    /**
     * Constructs a new, empty heap, ordered according to the given comparator.
     *
     *
     *
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     * @param d
     * the branching factor. Should be a power of 2.
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     */
    /**
     * Constructs a new, empty heap, using the natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     * @param d
     * the branching factor. Should be a power of 2.
     */
    init {
        this.size = 0
        this.root = null
        if (d < 2 || ((d and (d - 1)) != 0)) {
            throw IllegalArgumentException("Branching factor d should be a power of 2.")
        }
        this.d = d
        this.log2d = log2(d.toLong())
        this.aux = java.lang.reflect.Array.newInstance(Node::class.java, d) as Array<Node?>
    }

    @LogarithmicTime
    override fun insert(key: K, value: V?): Node {
        if (key == null) {
            throw NullPointerException("Null keys not permitted")
        }
        val n = Node(key, value, d)

        if (size == 0L) {
            root = n
            size = 1
            return n
        }

        val p = findNode(size)
        for (i in 0 until d) {
            if (p.children[i] == null) {
                p.children[i] = n
                break
            }
        }
        n.parent = p
        size++

        fixup(n)

        return n
    }

    @LogarithmicTime
    override fun insert(key: K): Node {
        return insert(key, null)
    }

    @ConstantTime
    override fun findMin(): Node {
        if (size == 0L) {
            throw NoSuchElementException()
        }
        return root!!
    }

    @LogarithmicTime
    override fun deleteMin(): Node {
        if (size == 0L) {
            throw NoSuchElementException()
        }

        val oldRoot  = root!!

        if (size == 1L) {
            root = null
            size = 0
        } else {
            root!!.delete()
        }

        return oldRoot
    }

    @get:ConstantTime
    override val isEmpty: Boolean
        get() {
            return size == 0L
        }

    @ConstantTime
    override fun size(): Long {
        return size
    }

    @ConstantTime
    override fun clear() {
        size = 0
        root = null
    }

    override fun comparator(): Comparator<in K?>? {
        return comparator
    }

    // handle
    inner class Node(override var key: K, override var value: V?, d: Int) : AddressableHeap.Handle<K, V>,
        Serializable {
        var parent: Node? = null
        //var children: Array<Node?> = java.lang.reflect.Array.newInstance(Node::class.java, d) as Array<Node>?
        var children: Array<Node?> = arrayOfNulls(d)

        @LogarithmicTime
        override fun decreaseKey(newKey: K) {
            if (parent == null && root !== this) {
                throw IllegalArgumentException("Invalid handle!")
            }
            val c: Int
            if (comparator == null) {
                c = (newKey as Comparable<K>).compareTo(key)
            } else {
                c = comparator.compare(newKey, key)
            }

            if (c > 0) {
                throw IllegalArgumentException("Keys can only be decreased!")
            }
            key = newKey
            if (c == 0 || root === this) {
                return
            }
            fixup(this)
        }

        @LogarithmicTime
        override fun delete() {
            if (parent == null && root !== this) {
                throw IllegalArgumentException("Invalid handle!")
            }

            if (size == 0L) {
                throw NoSuchElementException()
            }

            // swap with last node
            val last = findNode(size - 1)
            swap(this, last)

            // remove from parent
            if (this.parent != null) {
                for (i in 0 until d) {
                    if (parent!!.children[i] === this) {
                        parent!!.children[i] = null
                    }
                }
                this.parent = null
            }

            size--
            if (size == 0L) {
                root = null
            } else if (this !== last) {
                fixdown(last)
            }
        }
        
    }

    /**
     * Start at the root and traverse the tree in order to find a particular
     * node based on its numbering on a level-order traversal of the tree. Uses
     * the bit representation to keep the cost log_d(n).
     *
     * @param node
     * the node number assuming that the root node is number zero
     */
    private fun findNode(node: Long): Node {
        if (node == 0L) return root!!

        val mask: Long = d.toLong() - 1
        val location: Long = (node - 1)
        val log: Int = log2(node - 1) / log2d

        var cur: Node? = root
        for (i in log downTo 0) {
            val s: Int = i * log2d
            val path: Int = ((location and (mask shl s)) ushr s).toInt()
            val next: Node = cur!!.children[path] ?: break
            cur = next
        }
        return cur!!
    }

    /**
     * Calculate the floor of the binary logarithm of n.
     *
     * @param n
     * the input number
     * @return the binary logarithm
     */
    private fun log2(n: Long): Int {
        // returns 0 for n=0
        var n: Long = n
        var log: Long = 0
        if ((n and -0x100000000L) != 0L) {
            n = n ushr 32
            log = 32
        }
        if ((n and 0xffff0000L) != 0L) {
            n = n ushr 16
            log += 16
        }
        if (n >= 256) {
            n = n ushr 8
            log += 8
        }
        if (n >= 16) {
            n = n ushr 4
            log += 4
        }
        if (n >= 4) {
            n = n ushr 2
            log += 2
        }
        return (log + (n ushr 1)).toInt()
    }

    private fun fixup(n: Node) {
        if (comparator == null) {
            var p = n.parent
            while (p != null) {
                if ((n.key as Comparable<K>).compareTo(p.key) >= 0) {
                    break
                }
                val pp = p.parent
                swap(n, p)
                p = pp
            }
        } else {
            var p = n.parent
            while (p != null) {
                if (comparator.compare(n.key, p.key) >= 0) {
                    break
                }
                val pp = p.parent
                swap(n, p)
                p = pp
            }
        }
    }

    private fun fixdown(n: Node) {
        if (comparator == null) {
            while (n.children[0] != null) {
                var min: Int = 0
                var child = n.children[min]

                for (i in 1 until d) {
                    val candidate = n.children[i]
                    if (candidate != null && (candidate.key as Comparable<K>).compareTo(child!!.key) < 0) {
                        min = i
                        child = candidate
                    }
                }

                if ((n.key as Comparable<K>).compareTo(child!!.key) <= 0) {
                    break
                }
                swap(child, n)
            }
        } else {
            while (n.children[0] != null) {
                var min: Int = 0
                var child = n.children[min]

                for (i in 1 until d) {
                    val candidate = n.children[i]
                    if (candidate != null && comparator.compare(candidate.key, child!!.key) < 0) {
                        min = i
                        child = candidate
                    }
                }

                if (comparator.compare(n.key, child!!.key) <= 0) {
                    break
                }
                swap(child, n)
            }
        }
    }

    /**
     * Swap two nodes
     *
     * @param a
     * first node
     * @param b
     * second node
     */
    private fun swap(a: Node?, b: Node?) {
        var a: Node? = a
        var b: Node? = b
        if ((a == null) || (b == null) || (a === b)) {
            return
        }

        if (a.parent === b) {
            val tmp: Node = a
            a = b
            b = tmp
        }

        val pa = a.parent
        if (b.parent === a) {
            // a is the parent
            var whichChild: Int = -1
            for (i in 0 until d) {
                aux[i] = b.children[i]
                if (b === a.children[i]) {
                    b.children[i] = a
                    a.parent = b
                } else {
                    b.children[i] = a.children[i]
                    if (b.children[i] != null) {
                        b.children[i]!!.parent = b
                    }
                }
                if (pa != null && pa.children[i] === a) {
                    whichChild = i
                }
            }

            b.parent = pa
            if (pa != null) {
                pa.children[whichChild] = b
            }

            for (i in 0 until d) {
                a.children[i] = aux[i]
                if (a.children[i] != null) {
                    a.children[i]!!.parent = a
                }
                aux[i] = null
            }
        } else {
            // no parent child relationship
            val pb = b.parent
            for (i in 0 until d) {
                aux[i] = b.children[i]
                b.children[i] = a.children[i]
                if (b.children[i] != null) {
                    b.children[i]!!.parent = b
                }
            }
            for (i in 0 until d) {
                a.children[i] = aux[i]
                if (a.children[i] != null) {
                    a.children[i]!!.parent = a
                }
                aux[i] = null
            }
            var aIsChild: Int = -1
            if (pa != null) {
                for (i in 0 until d) {
                    if (pa.children[i] === a) {
                        aIsChild = i
                    }
                }
            } else {
                b.parent = null
            }
            var bIsChild: Int = -1
            if (pb != null) {
                for (i in 0 until d) {
                    if (pb.children[i] === b) {
                        bIsChild = i
                    }
                }
            } else {
                a.parent = null
            }
            if (aIsChild >= 0) {
                pa!!.children[aIsChild]= b
                b.parent = pa
            }
            if (bIsChild >= 0) {
                pb!!.children[bIsChild]= a
                a.parent = pb
            }
        }

        // switch root
        if (root === a) {
            root = b
        } else if (root === b) {
            root = a
        }
    }

    companion object {
        private val serialVersionUID: Long = 1
    }
}
